package class3;

import common.ListNode;
import common.ListNodeUtils;

/**
 * https://leetcode.cn/problems/middle-of-the-linked-list/
 * 题目：链表中间节点
 * 给你单链表的头结点 head ，请你找出并返回链表的中间结点。
 * 如果有两个中间结点，则返回第二个中间结点。
 * <p>
 * 解题思路：
 * 1.使用快慢指针，当快指针走到链表结尾时，慢指针刚好走到链表中间
 */
public class Code13_MidNode {
    public static void main(String[] args) {
        ListNode head = ListNodeUtils.getLinked(1, 2, 3, 4, 5, 6, 7);
        ListNode listNode = middleNode(head);
        ListNodeUtils.print(listNode);
        System.out.println();
        ListNode head2 = ListNodeUtils.getLinked(1, 2, 3, 4, 5, 6, 7);
        ListNode listNode1 = deleteMidNode(head2);
        ListNodeUtils.print(listNode1);
    }

    /**
     * 链表中间节点开始返回
     */
    public static ListNode middleNode(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode s = head;
        ListNode f = head;
        while (f != null) {
            s = s.next;
            f = f.next.next;
            if (f == null || f.next == null) {
                break;
            }
        }
        return s;
    }

    /**
     * 删除链表中的中间节点
     * 解题思路：
     * 1.需要记录目标节点target的前一个节点
     * 2.再将节点向后移
     * 3.当快指针走到尾时，刚好满指针走到中间
     */
    public static ListNode deleteMidNode(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode slow = head.next;
        ListNode fast = head.next.next;
        ListNode pre = null;
        while (fast != null && fast.next != null) {
            pre = slow; // 记录前一个节点
            slow = slow.next; // 慢指针走一步
            fast = fast.next.next; // 快指针走两步
        }
        System.out.println("pre:" + pre.val + "\t target:" + slow.val);
        if(pre!=null){
            pre.next = slow.next;
        }
        return head;
    }

}
